// https://www.lintcode.com/problem/ones-and-zeroes/description

class Solution {
public:
    /**
     * @param strs: an array with strings include only 0 and 1
     * @param m: An integer
     * @param n: An integer
     * @return: find the maximum number of strings
     */
    int findMaxForm(vector<string> &strs, int m, int n) {
        int k = strs.size();
        vector<vector<vector<int>>> res(k + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));
        vector<int> rec0(k, 0);
        vector<int> rec1(k, 0);
        for (int i = 0; i < m + 1; ++i)
        {
            for (int j = 0; j < n + 1; ++j)
            {
                res[0][i][j] = 0;
            }
        }
        for (int i = 0; i < k; ++i)
        {
            for (int j = 0; j < strs[i].length(); ++j)
            {
                if (strs[i][j] == '0')
                    rec0[i]++;
                else
                    rec1[i]++;
            }
        }
        for (int t = 1; t < k + 1; ++t)
        {
            for (int i = 0; i < m + 1; ++i)
            {
                for (int j = 0; j < n + 1; ++j)
                {
                    res[t][i][j] = res[t - 1][i][j];
                    if (i >= rec0[t - 1] && j >= rec1[t - 1])
                    {
                        res[t][i][j] = max(res[t][i][j], 
                        res[t - 1][i - rec0[t - 1]][j - rec1[t - 1]] + 1);
                    }
                }
            }
        }
        int maxVal = 0;
        for (int i = 0; i < m + 1; ++i)
        {
            for (int j = 0; j < n + 1; ++j)
            {
                maxVal = max(maxVal, res[k][i][j]);
            }
        }
        return maxVal;
    }
};